/*
 * =====================================================================================
 *
 *       Filename:  nth_smallest.c
 *
 *    Description:
 *
 *        Created:  2020-07-17 10:12
 *
 *         Author:  limingle
 *          Email:  lml@xdja.com
 *   Organization:  XDJA Tech.CO.ltd.
 *
 * =====================================================================================
 */

#include <stdio.h>

int partition(int a[], int from, int to)
{
    int i = from - 1;
    int j = from;
    while (j < to)
    {
        if (a[j] <= a[to])
        {
            i = i + 1;
            if (i != j)
            {
                a[i] ^= a[j];
                a[j] ^= a[i];
                a[i] ^= a[j];
            }
        }

        j = j + 1;
    }

    if (i + 1 != to)
    {
        a[i+1] ^= a[to];
        a[to] ^= a[i+1];
        a[i+1] ^= a[to];
    }

    return i + 1;
}

int nth_smallest(int a[], int from, int to, int nth)
{
    int p = partition(a, from, to);

    if (p == nth - 1)
    {
        return a[p];
    }

    if (p < nth - 1)
    {
        return nth_smallest(a, p + 1, to, nth - p - 1);
    }
    else
    {
        return nth_smallest(a, from, p - 1, nth);
    }
}

int main(int argc, const char *argv[])
{
    int a[] = {-4, 2, 10, 9, 8, 7, 6};
    int len = sizeof(a)/ sizeof(a[0]);

    printf("%d\n", nth_smallest(a, 0,  len - 1 , 3));

    return 0;
}
